package main

import "local/algorithm/util"

type ListNode = util.ListNode

/*
*
思路
类似于归并排序，
1.将全集一分为二，假设拆分后集合为a和b
2.对a,b再次执行拆分，直至a,b集合包含1个或0个链表
3.归并
*/
func mergeKLists(lists []*ListNode) *ListNode {
	l := len(lists)
	if l == 0 {
		return nil
	}

	if l == 1 {
		return lists[0]
	}

	m := l / 2
	left := mergeKLists(lists[:m])
	right := mergeKLists(lists[m:])
	return mergeTwoLinkedList(left, right)
}

func mergeTwoLinkedList(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	} else {
		if l1.Val < l2.Val {
			l1.Next = mergeTwoLinkedList(l1.Next, l2)
			return l1
		} else {
			l2.Next = mergeTwoLinkedList(l1, l2.Next)
			return l2
		}
	}
}
